//文件压缩-Huffman实现
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXSIZE 32

struct tnode {            //Huffman树结构
    char c;
    int weight;        //树节点权重，叶节点为字符和它的出现次数
    struct tnode *left, *right;
};
int Ccount[128] = {0};        //存放每个字符的出现次数，如Ccount[i]表示ASCII值为i的字符出现次数
struct tnode *Root = NULL;    //Huffman树的根节点
char HCode[128][MAXSIZE] = {{0}}; //字符的Huffman编码，如HCode['a']为字符a的Huffman编码（字符串形式）
int Step = 0;            //实验步骤
FILE *Src, *Obj;

void statCount();        //步骤1：统计文件中字符频率
void createHTree();        //步骤2：创建一个Huffman树，根节点为Root
void makeHCode();        //步骤3：根据Huffman树生成Huffman编码
void atoHZIP();        //步骤4：根据Huffman编码将指定ASCII码文本文件转换成Huffman码文件

void print1();            //输出步骤1的结果
void print2(struct tnode *p);    //输出步骤2的结果
void print3();            //输出步骤3的结果
void print4();            //输出步骤4的结果

int main() {
    if ((Src = fopen("input.txt", "r")) == NULL) {
        fprintf(stderr, "%s open failed!\n", "input.txt");
        return 1;
    }
    if ((Obj = fopen("output.txt", "w")) == NULL) {
        fprintf(stderr, "%s open failed!\n", "output.txt");
        return 1;
    }
    scanf("%d", &Step);        //输入当前实验步骤

    statCount();            //实验步骤1：统计文件中字符出现次数（频率）
    (Step == 1) ? print1() : 1;    //输出实验步骤1结果
    createHTree();            //实验步骤2：依据字符频率生成相应的Huffman树
    (Step == 2) ? print2(Root) : 2;    //输出实验步骤2结果
    makeHCode();        //实验步骤3：依据Root为树的根的Huffman树生成相应Huffman编码
    (Step == 3) ? print3() : 3;    //输出实验步骤3结果
    (Step >= 4) ? atoHZIP(), print4() : 4;//实验步骤4：据Huffman编码生成压缩文件，并输出实验步骤4结果

    fclose(Src);
    fclose(Obj);
    return 0;
}

//【实验步骤1】开始
void statCount() {
    Src = fopen("input.txt", "r");
    if (Src == NULL)
        return;
    char ch = 0;
    for (;;) {
        ch = fgetc(Src);
        //if (ch == EOF)
        //printf("发现EOF");
        //else if (ch == 0)
        //printf("发现0");
        if (ch == '\0')
            break;
        else if (ch == EOF)
            break;
        else if (ch != '\n')
            Ccount[ch - 0]++;
        Ccount[0] = 1;
        if (feof(Src))
            break;
    }
    //fclose(Src);
    //Src = NULL;
}



//【实验步骤1】结束

//【实验步骤2】开始
int cmp_heap(const void *p, const void *q) {
    struct tnode a = **(struct tnode **) p;
    struct tnode b = **(struct tnode **) q;
    if (a.weight > b.weight)
        return 1;
    else if (a.weight < b.weight)
        return -1;
    else if (a.c > b.c)
        return 1;
    else
        return -1;
}

void createHTree() {
    int i, j, k;
    struct tnode *p;
    struct tnode *heap[3000] = {0};
    int len_heap = 0;
    for (i = 0; i < 128; i++) {
        if (Ccount[i]) {
            p = (struct tnode *) malloc(sizeof(struct tnode));
            if (p == NULL) return;
            p->c = i;
            p->weight = Ccount[i];
            p->left = p->right = NULL;
            heap[len_heap++] = p;
        }
    }
    qsort(heap, len_heap, sizeof(struct tnode *), cmp_heap);
//    for (i = 0; i < len_heap; i++)
//        printf("%C %d\n", heap[i]->c, heap[i]->weight);
    while (len_heap > 1)//两两构建树的过程
    {
        struct tnode *t1 = heap[0];
        struct tnode *t2 = heap[1];
        for (i = 0; i < len_heap - 2; i++)
            heap[i] = heap[i + 2];
        len_heap -= 2;
        struct tnode *t = (struct tnode *) malloc(sizeof(struct tnode));
        if (t == NULL) return;
        t->c = -1;
        t->weight = t1->weight + t2->weight;
        t->left = t1;
        t->right = t2;
        //将 t插入到 数组中
        for (j = 0; j < len_heap; j++)
            if (heap[j]->weight > t->weight)
                break;
        for (k = len_heap; k > j; k--)
            heap[k] = heap[k - 1];
        heap[j] = t;
        len_heap++;
    }
    Root = heap[0];
}




//【实验步骤2】结束

//【实验步骤3】开始
void dfs(struct tnode *T, char s[]) {
    if (!T)return;
    if (T->left == NULL && T->right == NULL)
        strcpy(HCode[(int) (T->c)], s);
    else {
        if (T->left) {
            char tmp[MAXSIZE];
            strcpy(tmp, s);
            strcat(tmp, "0");
            dfs(T->left, tmp);

        }
        if (T->right) {
            char tmp[MAXSIZE];
            strcpy(tmp, s);
            strcat(tmp, "1");
            dfs(T->right, tmp);
        }
    }
}

void makeHCode() {
    char code[MAXSIZE] = {0};
    code[0] = '\0';
    //printf("%s", code);
    struct tnode *T = Root;
    dfs(T, code);
    //test(Root);
}





//【实验步骤3】结束

//【实验步骤4】开始
char buf[5000] = {0};

void atoHZIP() {
    int i;
    unsigned char tmp = 0;
    //char buf[1000] = { 0 };
    char ch = 0;
    rewind(Src);
    for (;;) {
        ch = fgetc(Src);
        if (ch == 0 || ch == EOF) {
            strcat(buf, HCode[0]);
            break;
        } else {
            strcat(buf, HCode[(int) ch]);
        }
    }
    int MOD = strlen(buf) % 8;
    if (MOD) {
        int diff = 8 - MOD;
        for (i = 0; i < diff; i++)
            strcat(buf, "0");
    }
    for (i = 0; buf[i] != '\0'; i++) {
        tmp = (tmp << 1) | (buf[i] - '0');
        if ((i + 1) % 8 == 0) {
            fputc(tmp, Obj);
            printf("%x", tmp);
            tmp = 0;
        }
    }

}




//【实验步骤4】结束

void print1() {
    int i;
    printf("NUL:1\n");
    for (i = 1; i < 128; i++)
        if (Ccount[i] > 0)
            printf("%c:%d\n", i, Ccount[i]);
}

void print2(struct tnode *p) {
    if (p != NULL) {
        if ((p->left == NULL) && (p->right == NULL))
            switch (p->c) {
                case 0:
                    printf("NUL ");
                    break;
                case ' ':
                    printf("SP ");
                    break;
                case '\t':
                    printf("TAB ");
                    break;
                case '\n':
                    printf("CR ");
                    break;
                default:
                    printf("%c ", p->c);
                    break;
            }
        print2(p->left);
        print2(p->right);
    }
}

void print3() {
    int i;

    for (i = 0; i < 128; i++) {
        if (HCode[i][0] != 0) {
            switch (i) {
                case 0:
                    printf("NUL:");
                    break;
                case ' ':
                    printf("SP:");
                    break;
                case '\t':
                    printf("TAB:");
                    break;
                case '\n':
                    printf("CR:");
                    break;
                default:
                    printf("%c:", i);
                    break;
            }
            printf("%s\n", HCode[i]);
        }
    }
}

void print4() {
    long int in_size, out_size;

    fseek(Src, 0, SEEK_END);
    fseek(Obj, 0, SEEK_END);
    in_size = ftell(Src);
    out_size = ftell(Obj);

    printf("\n原文件大小：%ldB\n", in_size);
    printf("压缩后文件大小：%ldB\n", out_size);
    printf("压缩率：%.2f%%\n", (float) (in_size - out_size) * 100 / in_size);
}

